pub struct BinaryTree<T> {
    root: *mut Node<T>,
}

impl<T> BinaryTree<T> {
    pub fn new(value: T) -> Self {
        BinaryTree {
            root: Node::new(value),
        }
    }

    // 提供安全的 set_left/set_right 方法
    pub fn set_left(&mut self, parent: *mut Node<T>, child: *mut Node<T>) {
        unsafe {
            (*parent).set_left(child);
        }
    }
}

impl<T> Drop for BinaryTree<T> {
    fn drop(&mut self) {
        unsafe {
            if !self.root.is_null() {
                Box::from_raw(self.root);
            }
        }
    }
}


use std::ptr;

// 二叉树节点
struct Node<T> {
    value: T,
    parent: *mut Node<T>, // 父节点（裸指针）
    left: *mut Node<T>,   // 左子节点
    right: *mut Node<T>,  // 右子节点
}

impl<T> Node<T> {
    fn new(value: T) -> *mut Self {
        // 在堆上分配节点，返回裸指针
        Box::into_raw(Box::new(Node {
            value,
            parent: ptr::null_mut(),
            left: ptr::null_mut(),
            right: ptr::null_mut(),
        }))
    }

    // 设置左子节点，并自动更新父节点
    unsafe fn set_left(&mut self, child: *mut Node<T>) {
        self.left = child;
        if !child.is_null() {
            (*child).parent = self as *mut Node<T>;
        }
    }

    // 设置右子节点，并自动更新父节点
    unsafe fn set_right(&mut self, child: *mut Node<T>) {
        self.right = child;
        if !child.is_null() {
            (*child).parent = self as *mut Node<T>;
        }
    }
}

// 手动实现 Drop 来释放整棵树
impl<T> Drop for Node<T> {
    fn drop(&mut self) {
        unsafe {
            // 递归释放左子树
            if !self.left.is_null() {
                Box::from_raw(self.left);
            }
            // 递归释放右子树
            if !self.right.is_null() {
                Box::from_raw(self.right);
            }
        }
    }
}

